from typing import List


class Solution:
    def maxProduct(self, words: List[str]) -> int:
        # 按长度排序单词，方便剪枝条件
        words.sort(key=lambda x: len(x), reverse=True)
        max_length = len(words[0])

        # 状态压缩
        stats = []
        for word in words:
            stat = 0
            for ch in word:
                stat |= 1 << (ord(ch) - 97)
            stats.append(stat)

        # 双层遍历计算答案
        ans = 0
        for i in range(len(words)):
            if len(words[i]) * max_length < ans:
                continue
            for j in range(i + 1, len(words)):
                if len(words[i]) * len(words[j]) < ans:
                    break
                if stats[i] & stats[j] == 0:
                    ans = max(ans, len(words[i]) * len(words[j]))
        return ans


if __name__ == "__main__":
    print(Solution().maxProduct(["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]))  # 16
    print(Solution().maxProduct(["a", "ab", "abc", "d", "cd", "bcd", "abcd"]))  # 4
    print(Solution().maxProduct(["a", "aa", "aaa", "aaaa"]))  # 0
